/**
 * @Question.Title: 寻找两个正序数组的中位数
 * @Question.No: 4
 * @Author: Dang Qi
 * @Date: 2021-04-27 11:28:56
 * @Description: 
 */
//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2
// 
//
// 示例 2： 
//
// 
//输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
// 
//
// 示例 3： 
//
// 
//输入：nums1 = [0,0], nums2 = [0,0]
//输出：0.00000
// 
//
// 示例 4： 
//
// 
//输入：nums1 = [], nums2 = [1]
//输出：1.00000
// 
//
// 示例 5： 
//
// 
//输入：nums1 = [2], nums2 = []
//输出：2.00000
// 
//
// 
//
// 提示： 
//
// 
// nums1.length == m 
// nums2.length == n 
// 0 <= m <= 1000 
// 0 <= n <= 1000 
// 1 <= m + n <= 2000 
// -106 <= nums1[i], nums2[i] <= 106 
// 
//
// 
//
// 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？ 
// Related Topics 数组 二分查找 分治算法 
// 👍 4029 👎 0

package dq.leetcode.editor.cn;

public class MedianOfTwoSortedArrays {
    public static void main(String[] args) {
        Solution solution = new MedianOfTwoSortedArrays().new Solution();
        int[] nums1 = {5,6};
        int[] nums2 = {3,4};
        System.out.println(solution.findMedianSortedArrays(nums1, nums2));
    }
        //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //保证左边的数量与右边相等或者比右边多一
        int totalLeft = (nums1.length + nums2.length + 1) / 2;
        if(nums1.length > nums2.length){
            int[] tmp = nums1;
            nums1 = nums2;
            nums2 = tmp;
        }
        int n1 = nums1.length;
        int n2 = nums2.length;
        int left = 0, right = n1;
        while (left < right){
            //i处于nums1的分界线右边一个数
            int i = left + (right - left + 1) / 2;
            //j处于nums1的分界线右边一个数
            int j = totalLeft - i;
            if(nums1[i-1] > nums2[j]){
                right = i - 1;
            }else{
                left = i;
            }
        }

        int i = left + (right - left + 1) / 2;
        int j = totalLeft - i;

        int n1_left = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int n1_right = i == n1 ? Integer.MAX_VALUE : nums1[i];
        int n2_left = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int n2_right = j == n2 ? Integer.MAX_VALUE : nums2[j];


        if((n1 + n2) % 2 == 1){
            return Math.max(n1_left, n2_left);
        }else{
            return (Math.max(n1_left, n2_left) + Math.min(n1_right, n2_right)) / 2.0;
        }
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}